1. Field of the Invention
This invention relates to error correction, in which in a digital communication system and a digital storage system, errors produced in a communication channel or a storage medium are corrected at the reception side using error correction codes. More particularly, the invention relates to a polynominal-set deriving apparatus and method, in which in a decoding operation using algebraic geometric codes as error correction codes, a set of minimal polynomials for generating a given multidimensional array corresponding to a syndrome in received words is obtained.
2. Description of the Related Art
RS (Reed-Solomon codes) codes and BCH (Bose-Chaudhuri-Hocquenghem) codes are well known as error correction codes for correcting errors produced in a communication channel or a storage medium at the reception side in a digital communication system and a digital storage system. These codes are actually used in apparatuses which deal with compact discs, satellite communication and the like.
Recently, however, codes named algebraic geometric codes utilizing the algebraic curve theory have been widely studied (see references (1)-(3)). Algebraic geometric codes belong to a code system which has a very wide applicational range, and which includes the above-described RS codes and BCH codes. It has gradually become clear that this system includes new codes having better properties than those of conventional codes (see reference (4)).
Decoding methods have always been a problem while such excellent codes have been discovered, and development of an efficient decoding algorithm has been requested. However, an efficient decoding algorithm has not been obtained at all until Justesen et al. have proposed a generalized Peterson algorithm (see reference (5)) in 1989. Justesen et al. have shown that by applying the Sakata algorithm (see reference (6)) proposed by Sakata to their generalized Peterson algorithm to provide an efficient algorithm for obtaining a two-dimensional linear feedback shift registers having a minimum number of storage elements, for generating a two-dimensional array having a given finite size, an error locator function can be derived at a high speed with a small amount of calculation.
However, since the generalized Peterson algorithm has a limitation in its correction capability, Skorobogatov et al. have proposed a Modified decoding algorithm (see reference (7)) which guarantees a higher correction capability.
Furthermore, since the Sakata algorithm includes a large amount of useless calculation not directly relating to the Modified decoding algorithm, Kamiya et al. have proposed an algorithm obtained by modifying the Sakata algorithm so as to conform to the Modified decoding algorithm in 1992 (see references (8) and (9)).
On the other hand, the Berlekamp-Massay algorithm (BM method) and the Euclidean algorithm (Eu method) are well known as conventional decoding methods for RS codes and BCH codes. The above-described generalized Peterson algorithm is an extension of the Peterson method used for decoding RS codes. The Sakata algorithm is also called a two-dimensional BM method, and is well known as an extension of the BM method used for decoding RS codes (hereinafter termed a one-dimensional BM method).
However, an algorithm corresponding to an extension of the Eu method used for decoding RS codes (hereinafter termed a one-dimensional EU method) has not previously been considered.
Although Sakata has also proposed a multidimensional BM method (see reference (10)) as an extension of the two-dimensional BM method, a multidimensional Eu method corresponding to that method has not been devised.
The multidimensional BM method is expressed by an algorithm having a structure as shown in FIG. 2 (see references (6) and (10) for a method of determining a defining point, rs, rt and the like).
Point n shown in FIG. 2 is updated by ordering termed a total order (see references (6) and (10)). In FIG. 2, the calculation of df.sub.n.sup.(i) in step S22 and the updating of f.sub.n.sup.(i) using h in step S25 are sequentially performed. This is because the calculation of df.sub.n.sup.(i) in step S22 at point n is performed using h obtained in step S24 at point n-1, and the updating of f.sub.n.sup.(i) using h in step S24 at point n is calculated using df.sub.n.sup.(i) in step S22 at point n. In this case, as shown in FIG. 12, a useless time is produced in the processing time, and therefore such a method is not efficient.
On the other hand, a method has been proposed, in which the processes of steps S22 and S24 are executed in parallel utilizing that processing for one-dimensional variables in the one-dimensional BM method, which is a decoding method for RS codes and BCH codes, is sequentially performed (see reference (11)). However, since this method uses shift registers having a fixed number of stages, (t+1) (t is the maximum value of the defining point at the final point (n=p: see FIG. 2) of polynomial f.sub.n.sup.(i)) processing clock pulses are always required for a single updating operation (cycle) of f.sub.n.sup.(i).
Accordingly, the apparatus of reference (9) requires useless processing clock pulses in the mid course of calculation (n&lt;p) of f.sub.n.sup.(i) which is not the largest defining point. Furthermore, the method of reference (9) does not consider the multidimensional BM method, and therefore is unsuitable for the multidimensional BM method in the following points:
1) Only one polynomial belongs to each of sets of polynomials F and G in the one-dimensional BM method, but a plurality of polynomials belong to each of sets of polynomials F and G in the multi-dimensional BM method. PA1 2) In the one-dimensional BM method, since the degrees of polynomials which belong to sets of polynomials F and G and the arrangement of a given array are one dimensional (one variable), respective coefficients can be sequentially stored in a one-dimensional memory (a shift register or the like) from the highest degree. However, since the degrees of polynomials and the arrangement of the array in the multi-dimensional BM method are not one-dimensional, efficient processing cannot be performed with a one-dimensional memory. PA1 3) In the one-dimensional BM method, since only one polynomial belongs to each of sets of polynomials F and G, parallel processing of polynomials is meaningless. In the multidimensional BM method, however, since a plurality of polynomials belong to each of sets of polynomials F and G, parallel processing of calculation of polynomials has a meaning. PA1 4) In the one-dimensional BM method, since only one variable is present in a polynomial which belongs to each of sets of polynomials F and G, the processes of steps S22 and S23 cannot be performed in parallel if calculation for one variable is performed in parallel. In the multidimensional BM method, however, since a plurality of variables are present in a polynomial which belongs to each of sets of polynomials F and G, the processes of steps S22 and S24 can be performed in parallel if calculation for one variable is performed in parallel.
References
(1) V. D. Goppa: "Codes on Algebraic Curves", Soviet Math. Dokl., 24, pp. 170-172, 1981.
(2) V. D. Goppa: "Algebraic-geometric Codes", Math. U.S.S.R. Izvestiya, vol. 21, No. 1, pp. 75-91, 1983.
(3) V. D. Goppa: "Geometry and Codes", Kluwer Academic Publishers, 1988.
(4) M. A. Tsfasman and S. G. Vladut: "Algebraic-geometric Codes", Kluwer Academic Publishers, 1991.
(5) J. Justesen, K. J. Larsen, E. Jensen, A. Havemose and T. Hoholdt: "Construction and Decoding of a Class of Algebraic Geometry Codes", IEEE Trans. Inform. Theory, vol. 35, No. 4, pp. 811-821, July, 1989.
(6) Sakata: "Synthesis of a Two-dimensional Linear Feedback Shift Register for Generating a Given Two-dimensional Array", Trans. of the Institute of Electronics and Communication Engineers of Japan (A), vol. J-70A, pp. 903-910, 1987.
(7) A. N. Skorobogatov and S. G. Vladut: "On the Decoding of Algebraic Geometric Codes", IEEE Trans. Inform. Theory, vol. 36, No. 5, pp. 1051-1060, September 1990.
(8) S. Sakata: "Extension of the Berlekamp-Massey Algorithm to N Dimensions", Information and Computation, vol. 84, pp. 207-239, 1990.
(9) Kamiya and Miura: "On the Application of the Sakata Algorithm for the Modified Decoding Algorithm Relating to Some Sort of Algebraic Curve Codes", Technical Report of the Institute of Electronics and Communication Engineers of Japan, vol. IT91, No. 435, IT91-96, pp. 47-54, 1992.
(10) Kamiya and Miura: "A Recurrent Decoding Algorithm Relating to Some Sort of Algebraic Curve Codes", Technical Report of the Institute of Electronics and Communication Engineers of Japan, vol. IT91, No. 505, IT91-116, pp. 89-96, 1992.
(11) Youzhi Xu: "Constributions to the Decoding of Reed-Solomon and Related Codes" Linkoping Studies in Science and Technology. Dissertations No. 257, 1991.